package fibonacci_problem

// 现在有一个棋盘，马从 0，0 触发，可以走 k 步 到 x,y 的位置，请问有多少种走法？
// 棋盘大小 10*9
func GetHorseToDestMethod(x, y, k int) int {
	if k == 0 { // base case
		if x == 0 && y == 0 {
			return 1
		}
		return 0
	}
	if x > 9 || y > 8 || x < 0 || y < 0 {
		return 0
	}
	return GetHorseToDestMethod(x-1, y+2, k-1) +
		GetHorseToDestMethod(x+1, y+2, k-1) +
		GetHorseToDestMethod(x+2, y+1, k-1) +
		GetHorseToDestMethod(x+2, y-1, k-1) +
		GetHorseToDestMethod(x+1, y-2, k-1) +
		GetHorseToDestMethod(x-1, y-2, k-1) +
		GetHorseToDestMethod(x-2, y-1, k-1) +
		GetHorseToDestMethod(x-2, y+1, k-1)
}


func GetHorseToDestMethodDp(x, y, k int) int {
	l := 10
	h := 9
	dp := make([][][]int, l)
	// 初始化三维的dp数组
	for i:=0; i<len(dp); i++ {
		dp[i] = make([][]int, h)
		for j:=0; j<h; j++ {
			dp[i][j] = make([]int, k+1)
		}
	}
	// 初始化初始值
	dp[x][y][0] = 1
	for z:=1; z<=k; z++ {
		for i:=0; i<l; i++ {
			for j:=0; j<h; j++ {
				dp[i][j][z] =
					GetValueByDp(dp, i-1, j+2, z-1) +
					GetValueByDp(dp, i+1, j+2, z-1) +
					GetValueByDp(dp, i+2, j+1, z-1) +
					GetValueByDp(dp, i+2, j-1, z-1) +
					GetValueByDp(dp, i+1, j-2, z-1) +
					GetValueByDp(dp, i-1, j-2, z-1) +
					GetValueByDp(dp, i-2, j-1, z-1) +
					GetValueByDp(dp, i-2, j+1, z-1)
			}
		}
	}
	return dp[0][0][k]
}

func GetValueByDp(dp [][][]int, x, y, z int) int {
	if x > 9 || y > 8 || x < 0 || y < 0 {
		return 0
	}
	return dp[x][y][z]
}